public class prog {
}
class Solution {
    public String removeOuterParentheses(String s) {
        StringBuilder sb=new StringBuilder();
        int sum=0;
        for(char ch : s.toCharArray()){
            if(ch==')'){
                sum--;
            }
            if(sum>=1){
                sb.append(ch);
            }
            if(ch=='('){
                sum++;
            }
        }
        return sb.toString();
    }
}










class Solution {
    public int matrixScore(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int res=0;
        for(int i=0;i<m;i++){
            if(grid[i][0]==0){
                for(int j=0;j<n;j++){
                    grid[i][j]=1-grid[i][j];
                }
            }
        }
        for(int j=0;j<n;j++){
            int count=0;
            for(int i=0;i<m;i++){
                count+=grid[i][j];
            }
            res+=Math.max(count,m-count)*(1<<(n-j-1));
        }
        return res;
    }
}










class Solution {
    public int findCenter(int[][] edges) {
        if(edges[0][0]==edges[1][0]){
            return edges[0][0];
        }else if(edges[0][0]==edges[1][1]){
            return edges[0][0];
        }
        return edges[0][1];
    }
}







class Solution {
    public int minOperations(int n) {
        return n*n/4;
    }
}







class Solution {
    public int minPairSum(int[] nums) {
        int max=0;
        Arrays.sort(nums);
        int i=0;
        int j=nums.length-1;
        while(i<j){
            int tmp=nums[i]+nums[j];
            max=Math.max(max,tmp);
            i++;
            j--;
        }
        return max;
    }
}









class Solution {
    public int maxDepth(String s) {
        int count=0;
        int max=0;
        for(char c: s.toCharArray()){
            if(c=='('){
                count++;
                max=Math.max(max,count);
            }else if(c==')'){
                count--;
            }
        }
        return max;
    }
}










class Solution {
    public int minTimeToVisitAllPoints(int[][] points) {
        int sum=0;
        for(int i=0,j=i+1;j<points.length;i++,j++){
            int x=Math.abs(points[j][0]-points[i][0]);
            int y=Math.abs(points[j][1]-points[i][1]);
            sum+=y>=x?y:x;
        }
        return sum;
    }
}










class Solution {
    public int findGCD(int[] nums) {
        Arrays.sort(nums);
        int max=nums[nums.length-1];
        int min=nums[0];
        if(max%min==0){
            return min;
        }else{
            int x=min;
            while(x!=0){
                if(min%x==0&&max%x==0){
                    return x;
                }
                x--;
            }
        }
        return 0;
    }
}











class ParkingSystem {
    int big;
    int medium;
    int small;
    public ParkingSystem(int big, int medium, int small) {
        this.big=big;
        this.medium=medium;
        this.small=small;
    }

    public boolean addCar(int carType) {
        if(carType==1){
            if(big>0){
                big--;
                return true;
            }
        }
        if(carType==2){
            if(medium>0){
                medium--;
                return true;
            }
        }
        if(carType==3){
            if(small>0){
                small--;
                return true;
            }
        }
        return false;
    }
}

/**
 * Your ParkingSystem object will be instantiated and called as such:
 * ParkingSystem obj = new ParkingSystem(big, medium, small);
 * boolean param_1 = obj.addCar(carType);
 */









class Solution {
    public int sumNums(int n) {
        boolean bool= n>0 && (n+=sumNums(n-1))>0;
        return n;
    }
}










class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res=new ArrayList<>();
        dfs("",n,n,res);
        return res;
    }
    public void dfs(String sb,int left,int right,List<String> res){
        if(left>right){
            return ;
        }
        if(left==0&&right==0){
            res.add(sb);
        }
        if(left>0){
            dfs(sb+'(',left-1,right,res);
        }
        if(right>0){
            dfs(sb+')',left,right-1,res);
        }
    }
}










class Solution {
    public int[] countPoints(int[][] points, int[][] queries) {
        int[] ans=new int[queries.length];
        int tmp=0;
        for(int i=0;i<queries.length;i++){
            for(int j=0;j<points.length;j++){
                if(Math.sqrt(Math.pow(Math.abs(queries[i][0]-points[j][0]),2) +Math.pow(Math.abs(queries[i][1]-points[j][1]),2)) <= queries[i][2]){
                    tmp++;
                }
            }
            ans[i]=tmp;
            tmp=0;
        }
        return ans;
    }
}










class Solution {
    public int minPartitions(String n) {
        int max=0;
        for(int i=0;i<n.length();i++){
            if(n.charAt(i)>max+48){
                max=n.charAt(i)-48;
            }
        }
        return max;
    }
}













class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> lists=new ArrayList<>();
        int n=nums.length;
        for(int i=0;i<Math.pow(2,n);i++){
            List<Integer> list=new ArrayList<>();
            int j=n;
            int v=i;
            while(j-- > 0){
                if((v&1)==1){
                    list.add(nums[j]);
                }
                v>>=1;
            }
            lists.add(list);
        }
        return lists;
    }
}










class Solution {
    public int[] getConcatenation(int[] nums) {
        int len=nums.length;
        int[] ans=new int[len*2];
        for(int i=0;i<len;i++){
            ans[i]=nums[i];
        }
        for(int i=len;i<len*2;i++){
            ans[i]=ans[i-len];
        }
        return ans;
    }
}









class Solution {
    public int[] buildArray(int[] nums) {
        int[] ans=new int[nums.length];
        for(int i=0;i<nums.length;i++){
            ans[i]=nums[nums[i]];
        }
        return ans;
    }
}









class Solution {
    public int divide(int dividend, int divisor) {
        long sum=0;
        long x=dividend;
        long y=divisor;
        boolean bool=(x<0&&y>0)||(x>0&&y<0);
        if(x<0){
            x=-x;
        }
        if(y<0){
            y=-y;
        }
        long left=0;
        long right=x;
        while(left<right){
            long mid=left+right+1>>1;
            if(Mul(mid,y)<=x){
                left=mid;
            }else{
                right=mid-1;
            }
        }
        sum=bool?-left:left;
        if(sum<Integer.MIN_VALUE||sum>Integer.MAX_VALUE){
            return Integer.MAX_VALUE;
        }
        return (int)sum;
    }
    public long Mul(long a,long b){
        long count=0;
        while(b>0){
            if((b&1)==1){
                count+=a;
            }
            a+=a;
            b>>=1;
        }
        return count;
    }
}











class Solution {
    public int balancedStringSplit(String s) {
        int count=0;
        int index=0;
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(ch=='L'){
                index++;
            }else{
                index--;
            }
            if(index==0){
                count++;
            }
        }
        return count;
    }
}
